/* 122. 买卖股票的最佳时机 II */
/**
 * @param {number[]} prices
 * @return {number}
 */

/* 贪心 */
var maxProfit = function (prices) {
    if (prices.length <= 1) return 0

    /* 只要今天比昨天大就卖出 */
    let maxPrice = 0
    for (let i = 1; i < prices.length; i++) {
        if (prices[i] > prices[i - 1]) {
            maxPrice += prices[i] - prices[i - 1]
        }
    }

    return maxPrice
};
/* 动态规划 */
var maxProfit = function (prices) {
    const n = prices.length
    const dp = new Array(n).fill(0).map(_ => new Array(2).fill(0))
    dp[0][0] = 0
    dp[0][1] = -prices[0]
    for (let i = 1; i < n; i++) {
        /* 最大收益 */
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
        /* 当天卖出和以前的收益做比较 */
        dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i])
    }
    return dp[i - 1][0]
}

/* 状态转移 */
var maxProfit = function (prices) {
    const n = prices.length
    let dp0 = 0, dp1 = -prices[0]

    for (let i = 1; i < n; i++) {
        let newDp0 = Math.max(dp0, dp1 + prices[i])
        let newDp1 = Math.max(dp1, dp0 - prices[i])

        dp0 = newDp0
        dp1 = newDp1
    }

    return dp0

}
maxProfit([7, 6, 4, 3, 1])